/**
 * GenerateAndReceive.java created by zhangzhidong 
 * at 下午8:48:59 2015年10月28日
 */
package algorithm.viterbi;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Random;

/**
 * 
 * 命令行运行方式:
 * 类存放路径algorithm/viterbi/GenerateAndReceive.class
 * cd /../../../bin
 * java algorithm.viterbi.GenerateAndReceive 1000 ~/Temp.txt
 * 运行参数如上,cd到放有algorithm的文件目录下面,然后输入上面一行参数,
 * 后面两个参数的含义是运行穷举法和Viterbi法各运行1000次,然后把结果打印到登陆账户HOME文件夹下面的Temp.txt文件中.
 * 如果第二个参数没有给出,则在控制台输出过程
 * 或者直接在Eclipse中Run as java application
 * 需要安装JDK来运行.class文件
 * 发送10个,收到12个,添加高斯噪声
 * @author zhangzhidong
 *
 */
public class Homework {
	Random rand = new Random(System.nanoTime());
	//h0=0.8 h1=0.4 h2=0.2
	public static double h0=0.8;
	public static double h1 =0.4;
	public static double h2= 0.2;
	public static double [][] H = new double [][]{
			{h0,0,0,0,0,0,0,0,0,0},
			{h1,h0,0,0,0,0,0,0,0,0},
			{h2,h1,h0,0,0,0,0,0,0,0},
			{0,h2,h1,h0,0,0,0,0,0,0},
			{0,0,h2,h1,h0,0,0,0,0,0},
			{0,0,0,h2,h1,h0,0,0,0,0},
			{0,0,0,0,h2,h1,h0,0,0,0},
			{0,0,0,0,0,h2,h1,h0,0,0},
			{0,0,0,0,0,0,h2,h1,h0,0},
			{0,0,0,0,0,0,0,h2,h1,h0},
			{0,0,0,0,0,0,0,0,h2,h1},
			{0,0,0,0,0,0,0,0,0 ,h2}
	};
	
	public static int M = H[0].length; //发送的数目
	public static int N = H.length;	   //接收的数目
	public static int STA = 3;
	public static int POSTIVE = +2;
	public static int NEGATIVE = -2;
	static int transition[][] = {
		{0,1},
		{2,3},
		{4,5},
		{6,7},
		{0,1},
		{2,3},
		{4,5},
		{6,7}
		
	};
	//等概率的生产-2与2
	private int generate(){
		
		return rand.nextInt(2)==0?-2:2;
	}
	public double noise(){
		double r =rand.nextGaussian();
		//OUT.println("***"+r+"***");
		return r;
	}
	public double[] generateSignal(){
		double x[] = new double[M];
		for(int i=0;i<x.length;i++){
			x[i] = (double)this.generate();
		}
		return x;
		
	}
	//计算H*x用来估计
	public static double []matrixMultply(double [][]X,double []y){
		double result [] =new double [X.length];
		for(int i=0;i<result.length;i++){
			for(int k =0;k<X[0].length;k++){
				result[i]+=X[i][k]*y[k];
			}
		}
		return result;
	}
	
	public static double matrixMultply(double []X,double []y){
		double result  =  0.0;
		for(int i=0;i<X.length;i++){
			result+=X[i]*y[i];
		}
		return result;
	}
	
	public double [] receive (PrintStream out){
		double signal[] = generateSignal();
		//这里打印出来产生的原始Signal
		out.println("产生的信号:");
		printArray(signal,out);
		//计算H*signal	
		double result[] = new double[N];
		for(int i=0;i<result.length;i++){
			for(int k =0;k<H[0].length;k++){
				//这里控制加不加噪声,以为噪声的类型
				result[i]+=H[i][k]*signal[k]+noise();
			}
		}
		
		return result;
		
	}
	public static  double distance(double []x ,double []y){
		double sum =0.0;
		for(int i=0;i<x.length;i++){
			sum+=(x[i]-y[i])*(x[i]-y[i]);
		}
		return sum;
	}
	//[0,k-1]计算距离
	public static  double distance(double []x ,double []y,int k){
		double sum =0.0;
		for(int i=0;i<k;i++){
			sum+=(x[i]-y[i])*(x[i]-y[i]);
		}
		return sum;
	}
	public static double distance (int tem[][][],int t,int flag,double receive[]){
		int i,j;
	    double tempd = 0;
	    for(i = 0; i < N; i++)
	    {
	        double tempdis = 0;
	        for(j = 0; j < M; j++)
	        tempdis += H[i][j] * tem[t][flag][j];
	        tempd += Math.abs(receive[i] - tempdis);
	    }
	    return tempd;
	}
	private double [] nextArray(double []x,int i){
		double result[] = new double [x.length];
		int k=0;
		int index=0;
		while(i>0){
			k=i%2;
			result[index]=k;
			i=i>>1;
			index++;
		}
		for(int z=0;z<result.length;z++){
			if((int)result[z]==0){
				result[z]=-2.0;
			}else{
				result[z]=2.0;
			}
		}
		return result;
	}
	/**
	 * 维特比译码
	 * 上午10:23:11 2015年10月30日
	 * @param receive 收到的序列
	 * @return
	 */
	public int [] viterbi (double receive[]){
		
		int i,j,k;
	    int delta[][][] =  new int [8][STA][M];
	    delta[0][0][0] = delta[0][0][1] = delta[0][0][2] = NEGATIVE;
	    delta[1][0][0] = POSTIVE;
	    delta[1][0][1] = delta[1][0][2] = NEGATIVE;
	    delta[2][0][0] = delta[2][0][2] = NEGATIVE; 
	    delta[2][0][1] = POSTIVE;
	    delta[3][0][0] = delta[3][0][1] = POSTIVE; 
	    delta[3][0][2] = NEGATIVE;
	    delta[4][0][0] = delta[4][0][1] = NEGATIVE;
	    delta[4][0][2] = POSTIVE;
	    delta[5][0][0] = delta[5][0][2] = POSTIVE;
	    delta[5][0][1] = NEGATIVE;
	    delta[6][0][0] = NEGATIVE; 
	    delta[6][0][1] = delta[6][0][2] = POSTIVE;
	    delta[7][0][0] = delta[7][0][1] = delta[7][0][2] = POSTIVE;
	   //动规
	    for(i = 3; i < M; i++){
	        for(j = 0; j < 8; j++){
	            for(k = 0;k < M; k++) 
	            	delta[j][1][k] = delta[j][2][k] = delta[j][0][k];  // 赋值初始状态
	        }
	        for(j = 0; j < 8; j++){
	            delta[j][1][i] = POSTIVE; 
	        	delta[j][2][i] = NEGATIVE;
	        }
	        for(j = 0; j < 8; j++){
	            int t[] = new int[]{0,0,0,0};
	            int index = 0;
	            for(k = 0; k < 8; k++)
	            for(int l = 0; l < 2; l++) {
	                if(transition[k][l] == j) {
	                    t[index++] = k;
	                    t[index++] = l;
	                }
	            }
	            if(distance(delta,t[0],t[1] + 1,receive) < distance(delta,t[2],t[3] + 1,receive))
	            	for(k = 0;k < M; k++) delta[j][0][k] = delta[t[0]][t[1] + 1][k];
	            else 
	            	for(k = 0; k < M; k++) delta[j][0][k] = delta[t[2]][t[3] + 1][k];
	        }
	    }
	    int deltabest[][][] =new int[1][3][M];
	    for(j = 0; j < M; j++) deltabest[0][0][j] = delta[0][0][j];
	    for(j = 1; j < 8; j++)
	    {
	        if(distance(deltabest,0,0,receive) > distance(delta,j,0,receive))
	        for(k = 0; k < M; k++) deltabest[0][0][k] = delta[j][0][k];
	    }	
		return deltabest[0][0];
	}
	
	/**
	 * 穷举法译码
	 */
	public double[] exhaust(double receive[]){
		double hatX[] = new double [10];//hatX 是穷举
		for(int i=0;i<hatX.length;i++){
			hatX[i]=-2.0;
		}
		int num=(int)Math.pow(2, hatX.length);
		double [] Satisfy = new double [hatX.length];
		double leastDistance = Double.MAX_VALUE;
		for(int i=0;i<num;i++){
			hatX = nextArray(hatX, i);
			double result [] = matrixMultply(H, hatX);
			//接收到的信号与穷举生成的信号之间的距离
			double res =distance(result, receive);
			if(res<leastDistance){
				leastDistance = res;
				Satisfy = hatX;
			}
			
		}	
		return Satisfy;
	}
	private static void printArray(double [] x,PrintStream out){
		for(int i=0;i<x.length;i++){
			out.print(x[i]);
			out.print(',');
		}
		out.println("<----");
	}
	private static void printArray(int [] x,PrintStream out){
		for(int i=0;i<x.length;i++){
			out.print(x[i]);
			out.print(',');
		}
		out.println("<----");
	}
	
	public static void main(String args[]) throws FileNotFoundException{
		Homework gar =  new Homework();
		PrintStream OUT = System.out;
		String path = null;
		int TIME = 1000;
		if(args.length==1){
			TIME = Integer.parseInt(args[0]);
		}else if(args.length==2){
			TIME = Integer.parseInt(args[0]);
			path  = args[1];
		}
		if(path!=null){
			File  f = new File(path);
			if(f.isFile()){
				System.out.println("数据打印到文件中");
				OUT =  new PrintStream(f);
				
			}
		}
		int k=TIME;
		long begin = System.currentTimeMillis();
		OUT.println("穷举法开始");
		while(k-->0){
			double []receive = gar.receive(OUT);
			OUT.println("接收到的结果:");
			printArray(receive,OUT);
			//输出穷举法的结果
			OUT.println("穷举译码的结果:");
			printArray(gar.exhaust(receive),OUT);
		}
		long end = System.currentTimeMillis();
	
		k=TIME;
		OUT.println("Viterbi开始");
		while(k-->0){
			double []receive = gar.receive(OUT);
			OUT.println("接收到的结果:");
			printArray(receive,OUT);
			//输出穷举法的结果
			OUT.println("Viterbi译码的结果:");
			printArray(gar.viterbi(receive),OUT);
		}
		long end2 = System.currentTimeMillis();
		OUT.println("穷举译码运行"+TIME+"次所需要的时间是:"+(end - begin )+"milliseconds");
		OUT.println("Viterbi译码运行"+TIME+"次所需要的时间是:"+(end2 - end )+"milliseconds");
		
	}
}
